package com.heima.leetcode.practice;

/**
 * leetcode 10 正则匹配
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/27 19:16
 */
public class E10 {
    /*
       a * b * c z .
     1 0 1 0 1 0 0 0
   a 0 1 1 0 1 0 0 0
   a 0 0 1 0 1 0 0 0
   a 0 0 1 0 1 0 0 0
   b 0 0 0 1 1 0 0 0
   c 0 0 0 0 0 1 0 0
   z 0 0 0 0 0 0 1 0
   y 0 0 0 0 0 0 0 1

   动态规划要从空字符串的情况开始考虑，不考虑会导致某些边界条件不符合
   dp[i][j] 表示源字符串前0 - i-1是否和模式字符串0 - j-1是否匹配，1表示true，0表示false
   注意空字符串和空模式是匹配的，空字符串和a*b*这类也是匹配的
   初始化第一行，第一列不用初始化，因为后面的源字符串有长度，肯定匹配不上空模式串

   初始化第一行：
   dp[0][0] = 1;
   if(pattern[j - 1] == '*'){
     dp[0][j] = dp[0][j - 2];
   }

   填充dp
   if(pattern[j - 1] != '*'){
     dp[i][j] = dp[i - 1][j - 1]
     && (source[i - 1] == pattern[j - 1] || pattern[j - 1] == '.');
   } else{
     dp[i][j] = dp[i][j - 2]
     || (dp[i-1][j] && source[i - 1] == pattern[j - 2])
     || (dp[i-1][j] && pattern[j - 2] == '.');
   }
 */

    /**
     * <h3>方法一：动态规划，最推荐</h3>
     * @param s 源字符串
     * @param p 模式串
     * @return 是否匹配
     */
    public boolean isMatch(String s, String p) {
        // 1. 将字符串和模式串转为字符数组
        char[] source = s.toCharArray();
        char[] pattern = p.toCharArray();
        int rows = source.length + 1;
        int cols = pattern.length + 1;
        // 2. 创建dp数组
        // dp[i][j] 表示 s 的前 0 - i-1 字符和 p 的前 0 - j-1 字符是否匹配
        boolean[][] dp = new boolean[rows][cols];
        // 3. 初始化第一行
        // 3.1空字符串与空模式是匹配的
        dp[0][0] = true;
        // 3.2初始化第一行，处理模式中的 '*' 可以匹配空串的情况
        for (int j = 2; j < cols; j++) {
            if(pattern[j - 1] == '*') dp[0][j] = dp[0][j - 2];
        }
        // 4. 填充dp
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                // 4.1 模式串当前字符不是*
                if (pattern[j - 1] != '*') {
                    dp[i][j] = dp[i - 1][j - 1] // 源字符串前面的要匹配上
                            && (source[i - 1] == pattern[j - 1] || pattern[j - 1] == '.'); // 源字符串当前的也要匹配上
                }
                // 4.2 模式串当前字符是*
                else {
                    dp[i][j] = dp[i][j - 2] // 如果*可以匹配0个
                            || (dp[i - 1][j] && source[i - 1] == pattern[j - 2]) // 源字符串不考虑当前字符能匹配上 并且 当前字符匹配上模式串中*前一个字符
                            || (dp[i - 1][j] && pattern[j - 2] == '.'); // 源字符串不考虑当前字符能匹配上 并且 当前字符匹配上模式串中*前一个字符
                }
            }
        }
        // 5. 返回结果
        return dp[rows - 1][cols - 1];
    }
}
